Many aspects of business operations involve hierarchies. For example, the relationships between business employees (e.g., reporting and the geographical) are hierarchical. Since these relationships are best represented by hierarchical data structures, a relational database system operated by a business may be required to maintain hierarchical data and support queries thereof.
Hierarchies may be represented in a database schema using a simple relational encoding. A common encoding is an adjacency list, in which a node of a hierarchy is represented by a row in a table and its parent node is identified by storing the parent node's primary key in a “parent” column in the row. FIG. 1 is an example of such a table, which encodes the hierarchy of FIG. 2. The parent column pid is a foreign key onto the primary key column id. For example, since node A1 is the parent node of B1, the row with id B1 specifies A1 in its pid column.
Querying hierarchical data of an adjacency list is inefficient. Accordingly, conventional systems facilitate queries by building a hierarchy index of the hierarchical data according to an indexing scheme. Such an index must be rebuilt when the underlying table of hierarchical data is updated (e.g., an entry in the pid column is updated, a new row is added to the table, etc.). Due to the potential sizes of tables of hierarchical data and the frequency with which hierarchy indexes must be rebuilt, efficient systems for building a hierarchy index are desired.